<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <title>src/world/IslandManager.js - p2.js</title>
    <link rel="stylesheet" href="http://yui.yahooapis.com/3.9.1/build/cssgrids/cssgrids-min.css">
    <link rel="stylesheet" href="../assets/vendor/prettify/prettify-min.css">
    <link rel="stylesheet" href="../assets/css/main.css" id="site_styles">
    <link rel="icon" href="../assets/favicon.ico">
    <script src="http://yui.yahooapis.com/combo?3.9.1/build/yui/yui-min.js"></script>
</head>
<body class="yui3-skin-sam">

<div id="doc">
    <div id="hd" class="yui3-g header">
        <div class="yui3-u-3-4">
                <h1><img src="../assets/css/logo.png" title="p2.js" width="117" height="52"></h1>
        </div>
        <div class="yui3-u-1-4 version">
            <em>API Docs for: 0.7.1</em>
        </div>
    </div>
    <div id="bd" class="yui3-g">

        <div class="yui3-u-1-4">
            <div id="docs-sidebar" class="sidebar apidocs">
                <div id="api-list">
                    <h2 class="off-left">APIs</h2>
                    <div id="api-tabview" class="tabview">
                        <ul class="tabs">
                            <li><a href="#api-classes">Classes</a></li>
                            <li><a href="#api-modules">Modules</a></li>
                        </ul>
                
                        <div id="api-tabview-filter">
                            <input type="search" id="api-filter" placeholder="Type to filter APIs">
                        </div>
                
                        <div id="api-tabview-panel">
                            <ul id="api-classes" class="apis classes">
                                <li><a href="../classes/AABB.html">AABB</a></li>
                                <li><a href="../classes/AngleLockEquation.html">AngleLockEquation</a></li>
                                <li><a href="../classes/Body.html">Body</a></li>
                                <li><a href="../classes/Box.html">Box</a></li>
                                <li><a href="../classes/Broadphase.html">Broadphase</a></li>
                                <li><a href="../classes/Capsule.html">Capsule</a></li>
                                <li><a href="../classes/Circle.html">Circle</a></li>
                                <li><a href="../classes/Constraint.html">Constraint</a></li>
                                <li><a href="../classes/ContactEquation.html">ContactEquation</a></li>
                                <li><a href="../classes/ContactMaterial.html">ContactMaterial</a></li>
                                <li><a href="../classes/Convex.html">Convex</a></li>
                                <li><a href="../classes/DistanceConstraint.html">DistanceConstraint</a></li>
                                <li><a href="../classes/Equation.html">Equation</a></li>
                                <li><a href="../classes/EventEmitter.html">EventEmitter</a></li>
                                <li><a href="../classes/FrictionEquation.html">FrictionEquation</a></li>
                                <li><a href="../classes/GearConstraint.html">GearConstraint</a></li>
                                <li><a href="../classes/GSSolver.html">GSSolver</a></li>
                                <li><a href="../classes/Heightfield.html">Heightfield</a></li>
                                <li><a href="../classes/Island.html">Island</a></li>
                                <li><a href="../classes/IslandManager.html">IslandManager</a></li>
                                <li><a href="../classes/IslandNode.html">IslandNode</a></li>
                                <li><a href="../classes/Line.html">Line</a></li>
                                <li><a href="../classes/LinearSpring.html">LinearSpring</a></li>
                                <li><a href="../classes/LockConstraint.html">LockConstraint</a></li>
                                <li><a href="../classes/Material.html">Material</a></li>
                                <li><a href="../classes/NaiveBroadphase.html">NaiveBroadphase</a></li>
                                <li><a href="../classes/Narrowphase.html">Narrowphase</a></li>
                                <li><a href="../classes/Object pooling utility..html">Object pooling utility.</a></li>
                                <li><a href="../classes/OverlapKeeper.html">OverlapKeeper</a></li>
                                <li><a href="../classes/OverlapKeeperRecord.html">OverlapKeeperRecord</a></li>
                                <li><a href="../classes/Particle.html">Particle</a></li>
                                <li><a href="../classes/Plane.html">Plane</a></li>
                                <li><a href="../classes/PrismaticConstraint.html">PrismaticConstraint</a></li>
                                <li><a href="../classes/Ray.html">Ray</a></li>
                                <li><a href="../classes/RaycastResult.html">RaycastResult</a></li>
                                <li><a href="../classes/RevoluteConstraint.html">RevoluteConstraint</a></li>
                                <li><a href="../classes/RotationalLockEquation.html">RotationalLockEquation</a></li>
                                <li><a href="../classes/.html"></a></li>
                                <li><a href="../classes/RotationalSpring.html">RotationalSpring</a></li>
                                <li><a href="../classes/RotationalVelocityEquation.html">RotationalVelocityEquation</a></li>
                                <li><a href="../classes/SAPBroadphase.html">SAPBroadphase</a></li>
                                <li><a href="../classes/Shape.html">Shape</a></li>
                                <li><a href="../classes/Solver.html">Solver</a></li>
                                <li><a href="../classes/Spring.html">Spring</a></li>
                                <li><a href="../classes/TopDownVehicle.html">TopDownVehicle</a></li>
                                <li><a href="../classes/TupleDictionary.html">TupleDictionary</a></li>
                                <li><a href="../classes/Utils.html">Utils</a></li>
                                <li><a href="../classes/vec2.html">vec2</a></li>
                                <li><a href="../classes/WheelConstraint.html">WheelConstraint</a></li>
                                <li><a href="../classes/World.html">World</a></li>
                            </ul>
                
                            <ul id="api-modules" class="apis modules">
                            </ul>
                        </div>
                    </div>
                </div>
            </div>
        </div>
        <div class="yui3-u-3-4">
                <div id="api-options">
                    Show:
                    <label for="api-show-inherited">
                        <input type="checkbox" id="api-show-inherited" checked>
                        Inherited
                    </label>
            
                    <label for="api-show-protected">
                        <input type="checkbox" id="api-show-protected">
                        Protected
                    </label>
            
                    <label for="api-show-private">
                        <input type="checkbox" id="api-show-private">
                        Private
                    </label>
                    <label for="api-show-deprecated">
                        <input type="checkbox" id="api-show-deprecated">
                        Deprecated
                    </label>
            
                </div>
            
            <div class="apidocs">
                <div id="docs-main">
                    <div class="content">
<h1 class="file-heading">File: src/world/IslandManager.js</h1>

<div class="file">
    <pre class="code prettyprint linenums">
var vec2 = require(&#x27;../math/vec2&#x27;)
,   Island = require(&#x27;./Island&#x27;)
,   IslandNode = require(&#x27;./IslandNode&#x27;)
,   IslandNodePool = require(&#x27;./../utils/IslandNodePool&#x27;)
,   IslandPool = require(&#x27;./../utils/IslandPool&#x27;)
,   Body = require(&#x27;../objects/Body&#x27;);

module.exports = IslandManager;

/**
 * Splits the system of bodies and equations into independent islands
 *
 * @class IslandManager
 * @constructor
 * @param {Object} [options]
 * @extends Solver
 */
function IslandManager(options){

    /**
     * @property nodePool
     * @type {IslandNodePool}
     */
    this.nodePool = new IslandNodePool({ size: 16 });

    /**
     * @property islandPool
     * @type {IslandPool}
     */
    this.islandPool = new IslandPool({ size: 8 });

    /**
     * The equations to split. Manually fill this array before running .split().
     * @property {Array} equations
     */
    this.equations = [];

    /**
     * The resulting {{#crossLink &quot;Island&quot;}}{{/crossLink}}s.
     * @property {Array} islands
     */
    this.islands = [];

    /**
     * The resulting graph nodes.
     * @property {Array} nodes
     */
    this.nodes = [];

    /**
     * The node queue, used when traversing the graph of nodes.
     * @private
     * @property {Array} queue
     */
    this.queue = [];
}

/**
 * Get an unvisited node from a list of nodes.
 * @static
 * @method getUnvisitedNode
 * @param  {Array} nodes
 * @return {IslandNode|boolean} The node if found, else false.
 */
IslandManager.getUnvisitedNode = function(nodes){
    var Nnodes = nodes.length;
    for(var i=0; i!==Nnodes; i++){
        var node = nodes[i];
        if(!node.visited &amp;&amp; node.body.type === Body.DYNAMIC){
            return node;
        }
    }
    return false;
};

/**
 * Visit a node.
 * @method visit
 * @param  {IslandNode} node
 * @param  {Array} bds
 * @param  {Array} eqs
 */
IslandManager.prototype.visit = function (node,bds,eqs){
    bds.push(node.body);
    var Neqs = node.equations.length;
    for(var i=0; i!==Neqs; i++){
        var eq = node.equations[i];
        if(eqs.indexOf(eq) === -1){ // Already added?
            eqs.push(eq);
        }
    }
};

/**
 * Runs the search algorithm, starting at a root node. The resulting bodies and equations will be stored in the provided arrays.
 * @method bfs
 * @param  {IslandNode} root The node to start from
 * @param  {Array} bds  An array to append resulting Bodies to.
 * @param  {Array} eqs  An array to append resulting Equations to.
 */
IslandManager.prototype.bfs = function(root,bds,eqs){

    // Reset the visit queue
    var queue = this.queue;
    queue.length = 0;

    // Add root node to queue
    queue.push(root);
    root.visited = true;
    this.visit(root,bds,eqs);

    // Process all queued nodes
    while(queue.length) {

        // Get next node in the queue
        var node = queue.pop();

        // Visit unvisited neighboring nodes
        var child;
        while((child = IslandManager.getUnvisitedNode(node.neighbors))) {
            child.visited = true;
            this.visit(child,bds,eqs);

            // Only visit the children of this node if it&#x27;s dynamic
            if(child.body.type === Body.DYNAMIC){
                queue.push(child);
            }
        }
    }
};

/**
 * Split the world into independent islands. The result is stored in .islands.
 * @method split
 * @param  {World} world
 * @return {Array} The generated islands
 */
IslandManager.prototype.split = function(world){
    var bodies = world.bodies,
        nodes = this.nodes,
        equations = this.equations;

    // Move old nodes to the node pool
    while(nodes.length){
        this.nodePool.release(nodes.pop());
    }

    // Create needed nodes, reuse if possible
    for(var i=0; i!==bodies.length; i++){
        var node = this.nodePool.get();
        node.body = bodies[i];
        nodes.push(node);
        // if(this.nodePool.length){
        //     var node = this.nodePool.pop();
        //     node.reset();
        //     node.body = bodies[i];
        //     nodes.push(node);
        // } else {
        //     nodes.push(new IslandNode(bodies[i]));
        // }
    }

    // Add connectivity data. Each equation connects 2 bodies.
    for(var k=0; k!==equations.length; k++){
        var eq=equations[k],
            i=bodies.indexOf(eq.bodyA),
            j=bodies.indexOf(eq.bodyB),
            ni=nodes[i],
            nj=nodes[j];
        ni.neighbors.push(nj);
        nj.neighbors.push(ni);
        ni.equations.push(eq);
        nj.equations.push(eq);
    }

    // Move old islands to the island pool
    var islands = this.islands;
    for(var i=0; i&lt;islands.length; i++){
        this.islandPool.release(islands[i]);
    }
    islands.length = 0;

    // Get islands
    var child;
    while((child = IslandManager.getUnvisitedNode(nodes))){

        // Create new island
        var island = this.islandPool.get();

        // Get all equations and bodies in this island
        this.bfs(child, island.bodies, island.equations);

        islands.push(island);
    }

    return islands;
};

    </pre>
</div>
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>
<script src="../assets/vendor/prettify/prettify-min.js"></script>
<script>prettyPrint();</script>
<script src="../assets/js/yui-prettify.js"></script>
<script src="../assets/../api.js"></script>
<script src="../assets/js/api-filter.js"></script>
<script src="../assets/js/api-list.js"></script>
<script src="../assets/js/api-search.js"></script>
<script src="../assets/js/apidocs.js"></script>
</body>
</html>
